/**
 * @Author Fizz Pu
 * @Date 2020/9/10 上午6:51
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.*;

/**
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 示例 1:
 *
 * 输入: n = 12
 * 输出: 3
 * 解释: 12 = 4 + 4 + 4.
 * 示例 2:
 *
 * 输入: n = 13
 * 输出: 2
 * 解释: 13 = 4 + 9.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/perfect-squares
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Lee279 {
    public static void main(String[] args) {
        System.out.println(new Lee279().numSquares(12));
        System.out.println(new Lee279().numSquares(13));
        System.out.println(new Lee279().numSquares(4));
    }
    // 0 到 n 构成图的节点，如果两个节点之间差一个完全平方数，那么就在之间连一条线
    // 搜索最小路径，则使用宽度优先搜索。
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        queue.add(n);
        set.add(n);
        int count = 0;
        while (!queue.isEmpty()){
            ++count;
            int size = queue.size();
            // for(int k = 0; k < queue.size(); ++k) error!
            for(int k = 0; k < size; ++k){
                int node = queue.remove(); // 取队头元素并删除
                // 后面再使用贪心算法优化
                int j;
//                for(int i = 1; (j = i * i) <= n; ++i){
//                    int next = node - j;
//                    if(next == 0)return count;
//                    else if  (next > 0) queue.add(next);
//                    else break;
//                }
                for(int i = node; i >= 1; --i){
                    if(isSquare(i)){
                        int next = node - i;
                        if(next == 0)return count;
                        else if (set.contains(next)){}
                        else {
                            set.add(next);
                            queue.add(next);
                        }
                }
            }
         }
        }
        return  -1;
    }

    static boolean  isSquare(int num){
        int j = (int)Math.sqrt(num);
        return j*j == num;
    }
}
